package arrayList_3_12;

public class MyArrayList {
    //这个数组存储顺序表中的元素
    private String[] data = null;
    //表示顺序表中的有效元素个数
    private int size = 0;

    //误餐构造，默认空间容量为10
    public MyArrayList(){
        data = new String[10];
    }
    //有参构造，capacity小于10，默认容量为10，否则空间容量按capacity开空间
    public MyArrayList(int capacity){
        if(capacity < 10){
            capacity = 10;
        }
        data = new String[capacity];
    }

    //按1.5倍扩容
    private void resize(){
        //按1.5倍创建更长数组
        String[] newData = new String[size + size>>1];
        //将旧数组的元素拷贝到新数组中
        for(int i = 0; i < size; i++){
            newData[i] = data[i];
        }
        //将新数组替换旧数组
        data = newData;
    }
    //尾插
    public void add(String elem){
        //判断空间容量是否满，满则扩容
        if(size == data.length){
            resize();
        }
        data[size] = elem;
        size++;  //增加有效元素个数
    }
    //按下标插入元素
    public void add(int index, String elem){
        //检查下标是否合法
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
        //检查是否需要扩容
        if(size == data.length){
            resize();
        }
        //从后往前遍历，将[index, size)上的元素后移一个位置
        for(int i = size - 1; i >= index; i--){
            data[i + 1] = data[i];
        }
        data[index] = elem; //在index处插入新元素
        size++; //增加有效元素个数
    }
    //删除index处的元素
    public String remove(int index){
        //检查下标是否合法
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
        //记录要删除的元素
        String ret = data[index];
        //从前往后遍历，将[index + 1, size)上的元素前移一个位置
        for(int i = index; i < size - 1; i++){
            data[i] = data [i + 1];
        }
        size--; //减少有效元素个数
        return ret;
    }
    //删除指定的第一个元素
    public boolean remove(String elem){
        //从左往右找第一个待删除元素的下标
        for(int i = 0; i < size; i++){
            //找到第一个待删除的元素
            if(data[i].equals(elem)){
                //删除下标为i的元素
                remove(i);
                return true;   //删除成功返回true
            }
        }
        return false;   //未找到待删除元素，删除失败，返回false
    }
    //获取下标index处的元素
    public String get(int index){
        //检查下标是否合法
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
        return data[index];
    }
    //将下标index处的元素设置为elem
    public void set(int index, String elem){
        //检查下标是否合法
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("index:" + index + " size:" + size);
        }
        data[index] = elem;
    }
    //清空顺序表
    public void clear(){
        size = 0;
    }

    //判断elem是否在顺序表中，在返回true，不在返回false
    public boolean contains(String elem){
//        //遍历，看elem是否存在，在返回true，不在返回false
//        for(int i = 0; i < size; i++){
//            if (data[i].equals(elem)){
//                return true;
//            }
//        }
//        return false;
        return indexOf(elem) != -1;
    }
    //返回第一个elem的下标，在返回下标，不在返回-1
    public int indexOf(String elem){
        for(int i = 0; i < size; i++){
            if(data[i].equals(elem)){
                return i;
            }
        }
        return -1;
    }
    //返回最后一个elem的下标，在返回下标，不在返回-1
    public int lastIndexOf(String elem){
        for(int i = size - 1; i >= 0; i--){
            if(data[i].equals(elem)){
                return i;
            }
        }
        return -1;
    }
    //截取下标[formIndex，toIndex)上的元素
    public MyArrayList subList(int formIndex, int toIndex){
        //判断下标是否合法
        if(formIndex < 0 || toIndex > size || formIndex > toIndex){
            throw new IndexOutOfBoundsException("formIndex:" + formIndex +
                    " toIndex:" + toIndex + " size:" + size);
        }
        //创建一个顺序表
        MyArrayList sublist = new MyArrayList();
        //下标[formIndex，toIndex)的元素拷贝到sublist
        for(int i = formIndex; i < toIndex; i++){
            sublist.add(data[i]);
        }
        return sublist;
    }
    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++){
            stringBuilder.append(data[i]);
            if(i != size - 1){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
